//题目:
// 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 子数组是数组中的一个连续部分。
#include<iostream>
#include<limits.h>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int maxSubArray(vector<int>& nums) 
    {
        int n=nums.size();
        //1.创建dp表————dp[i]表示以nums[i]为结尾的连续子数组最大和
        vector<int> dp(n);
        //2.初始化啊
        dp[0]=nums[0];
        //3.填表————动态转移方程：dp[i]=nums[i]+max(0,dp[i-1]);
        for(int i=1;i<n;i++)
            dp[i]=nums[i]+max(0,dp[i-1]);
        //4.确定返回值
        int ret=INT_MIN;
        for(int i=0;i<n;i++)
            ret=max(ret,dp[i]);
        return ret;
    }
};